package leetcode_zh

/**
 * @Description: 92. 反转链表 II 中等
 * @Keyword: 递归
 * @Author: kami
 * @Date: 2022/5/27 11:45
 **/
func reverseBetween(head *ListNode, left int, right int) *ListNode {
	var (
		// 记录左前节点，右后节点
		leftPre   *ListNode
		leftNode  *ListNode
		rightNode *ListNode
		rightNext *ListNode
	)

	var reshead = head
	var cnt = 1
	for head != nil {
		if cnt == left {
			leftNode = head
		}
		if cnt == right {
			rightNode = head
			rightNext = rightNode.Next
		}

		if cnt >= right {
			break
		}

		if cnt < left {
			leftPre = head
		}

		head = head.Next
		cnt++
	}
	rightNode.Next = nil
	var reversehead = reverseNode(leftNode)
	if leftPre != nil {
		leftPre.Next = reversehead
	}
	leftNode.Next = rightNext
	if left == 1 {
		return reversehead
	}
	return reshead
}

func reverseNode(node *ListNode) *ListNode {
	if node.Next == nil {
		return node
	}
	var res = reverseNode(node.Next)

	node.Next.Next = node

	return res
}

/**
 * @Description: 82. 删除排序链表中的重复元素 II 中等
 * @Keyword: 一次遍历
 * @Author: kami
 * @Date: 2022/5/27 12:53
 **/
func deleteDuplicates(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	dummy := &ListNode{0, head}
	cur := dummy
	for cur.Next != nil && cur.Next.Next != nil {
		if cur.Next.Val == cur.Next.Next.Val {
			x := cur.Next.Val
			for cur.Next != nil && cur.Next.Val == x {
				cur.Next = cur.Next.Next
			}
		} else {
			cur = cur.Next
		}
	}

	return dummy.Next
}

/**
 * @Description: 83. 删除排序链表中的重复元素 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/5/27 18:11
 **/
func deleteDuplicates82(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	dummy := &ListNode{-101, head}
	cur := dummy
	for cur.Next != nil {
		for cur.Next != nil && cur.Val == cur.Next.Val {
			cur.Next = cur.Next.Next
		}
		if cur == nil || cur.Next == nil {
			return dummy.Next
		}
		cur = cur.Next
	}

	return dummy.Next
}

/**
 * @Description: 24. 两两交换链表中的节点 中等
 * @Keyword: 不能修改节点内部值 只能修改引用
 * @Author: kami
 * @Date: 2022/5/29 17:55
 **/
func swapPairs(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	var resHead = head.Next
	var preHead = head
	for head.Next != nil {
		// 保存下一组头节点
		var nextNext = head.Next.Next
		// 上一组的后续指向本组第二个
		preHead.Next = head.Next
		// 本组第二个指向第一个
		head.Next.Next = head
		// 本组第一个指向下一组头结点
		head.Next = nextNext

		// 后续一组不满2个
		if nextNext == nil {
			return resHead
		}
		// 指针推进
		preHead = head
		head = nextNext
	}
	return resHead
}

/**
 * @Description: 141. 环形链表 简单
 * @Keyword: 快慢指针法
 * @Author: kami
 * @Date: 2022/6/7 17:51
 **/
func hasCycle(head *ListNode) bool {
	if head == nil || head.Next == nil || head.Next.Next == nil {
		return false
	}
	var quickNode = head.Next.Next
	var slowNode = head
	for slowNode != quickNode {
		if slowNode == nil || quickNode == nil || quickNode.Next == nil {
			return false
		}
		slowNode = slowNode.Next
		quickNode = quickNode.Next.Next
	}
	return true
}

/**
 * @Description: 142. 环形链表 II 中等
 * @Keyword: 快指针走的距离是满指针的2倍 2*（a+b） = a + b+ c +b ,a=c
 * @Author: kami
 * @Date: 2022/6/8 12:15
 **/
func detectCycle(head *ListNode) *ListNode {
	slow, fast := head, head
	for fast != nil {
		slow = slow.Next
		if fast.Next == nil {
			return nil
		}
		fast = fast.Next.Next
		if fast == slow {
			p := head
			for p != slow {
				p = p.Next
				slow = slow.Next
			}
			return p
		}
	}
	return nil
}

/**
 * @Description: 148. 排序链表
 * @Keyword: 插入排序 会超时
 * @Author: kami
 * @Date: 2022/6/8 12:45
 **/
func sortList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	newHead := head
	tail := head
	curNode := head.Next
	tail.Next = nil
	for curNode != nil {
		curNext := curNode.Next
		var tmpNode = newHead
		var preNode *ListNode
		var nextNode = newHead
		for tmpNode != nil && curNode.Val > tmpNode.Val {
			preNode = tmpNode
			nextNode = tmpNode.Next
			tmpNode = tmpNode.Next
		}
		// 当前待排序节点应放置在有序列表的尾结点
		if tmpNode == nil {
			tail.Next = curNode
			tail = tail.Next
			tail.Next = nil
		} else if curNode.Val <= newHead.Val {
			// 当前待排序节点应放置在有序列表的头结点
			curNode.Next = newHead
			newHead = curNode
		} else {
			// 当前待排序节点在有序列表的内部节点
			preNode.Next = curNode
			curNode.Next = nextNode
		}
		curNode = curNext
	}
	return newHead
}

/**
 * @Description: 148. 排序链表
 * @Keyword: 归并排序
 * @Author: kami
 * @Date: 2022/6/8 12:45
 **/
func sortListMerge(head *ListNode) *ListNode {
	return sortNode(head, nil)
}

func sortNode(head, tail *ListNode) *ListNode {
	if head == nil {
		return head
	}

	if head.Next == tail {
		head.Next = nil
		return head
	}

	slow, fast := head, head
	for fast != tail {
		slow = slow.Next
		fast = fast.Next
		if fast != tail {
			fast = fast.Next
		}
	}

	mid := slow
	return merge148(sortNode(head, mid), sortNode(mid, tail))
}

func merge148(head1, head2 *ListNode) *ListNode {
	dummyHead := &ListNode{}
	temp, temp1, temp2 := dummyHead, head1, head2
	for temp1 != nil && temp2 != nil {
		if temp1.Val <= temp2.Val {
			temp.Next = temp1
			temp1 = temp1.Next
		} else {
			temp.Next = temp2
			temp2 = temp2.Next
		}
		temp = temp.Next
	}
	if temp1 != nil {
		temp.Next = temp1
	} else if temp2 != nil {
		temp.Next = temp2
	}
	return dummyHead.Next
}

/**
 * @Description: 234. 回文链表 简单
 * @Keyword: 存储节点
 * @Author: kami
 * @Date: 2022/6/10 14:41
 **/
func isPalindrome234(head *ListNode) bool {
	var nums []int
	var curNode = head
	for curNode != nil {
		nums = append(nums, curNode.Val)
		curNode = curNode.Next
	}
	var idx = len(nums) - 1
	for idx >= 0 {
		if head.Val != nums[idx] {
			return false
		}
		idx--
		head = head.Next
	}
	return true
}
